package main

var (
	dx = []int{1, 0, 0, -1}
	dy = []int{0, 1, -1, 0}
)

func exist(board [][]byte, word string) bool {
	n := len(board)
	m := len(board[0])
	firsts := [][]int{}
	first := word[0]
	//初始化起始节点
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if board[i][j] == first {
				firsts = append(firsts, []int{i, j})
			}
		}
	}
	//遍历开始字符
	for i := 0; i < len(firsts); i++ {
		//初始化使用标记
		used := make([][]bool, n)
		for i := 0; i < n; i++ {
			used[i] = make([]bool, m)
		}
		start := firsts[i]
		w := []byte{}
		w = append(w, word[0])
		queue := [][]int{}
		queue = append(queue, start)
		index := 1
		for i := 0; i < len(queue); i++ {
			node := queue[i]
			for j := 0; j < 4; j++ {
				x := node[0] + dx[j]
				y := node[1] + dy[j]
				if x >= 0 && x < m && y >= 0 && y < n && !used[y][x] {
					used[y][x] = true
					if len(word) > index && board[y][x] == word[index] {
						w = append(w, word[index])
						queue = append(queue, []int{x, y})
						index++
					}
				}
			}
		}
		if word == string(w) {
			return true
		}
	}
	return false
}

func main() {
	strs := [][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}
	exist(strs, "ABCCED")
}
